class Solution:
    def minimumSubstringsInPartition(self, s: str) -> int:
        nowLen = [len(s)] * len(s)
        for i in range(0, len(s)):
            nowDict = {}
            for j in range(i, -1, -1):
                old = nowDict.get(s[j])
                if old is None:
                    old = 0
                nowDict[s[j]] = old + 1
                if j == 0:
                    if is_partition(nowDict):
                        nowLen[i] = 1
                elif is_partition(nowDict):
                    nowLen[i] = min(nowLen[j - 1] + 1, nowLen[i])
                # print(i, j)
        return nowLen[len(s)-1]

def is_partition(d: dict) -> bool:
    if len(d) == 0 or len(d) == 1:
        return True
    v = None
    for value in d.values():
        if v is None:
            v = value
        elif v != value:
            return False
    return True


if __name__ == '__main__':
    nums = "abababaccddb"
    s = Solution()

    print(s.minimumSubstringsInPartition(nums))
